#define _CRT_SECURE_NO_WARNINGS
#include<math.h>
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode {
    int val;
    struct ListNode* next;
 };
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
    struct ListNode* tailA = headA;
    struct ListNode* tailB = headB;
    int lenA = 1;
    int lenB = 1;
    if (headA == NULL || headB == NULL)
    {
        return NULL;
    }
    while (tailA->next)
    {
        tailA = tailA->next;
        lenA++;
    }
    while (tailB->next)
    {
        tailB = tailB->next;
        lenB++;
    }
    if (tailA != tailB)
    {
        return NULL;
    }
     //else
     //{
     //    return headA->next->next;
     //}
    else
    {
        struct ListNode* longhead = headA;
        struct ListNode* shorthed = headB;
        int len = abs(lenA - lenB);
        if (lenA < lenB)
        {
            longhead = headB;
            shorthed = headA;
        }

        while (len--)
        {
            longhead = longhead->next;
        }
        while (longhead)
        {
            if (longhead != shorthed)
            {
                longhead = longhead->next;
                shorthed = shorthed->next;
            }
            else
            {
                return longhead;
            }

        }
    }
    return NULL;
}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return true;
        }
    }
    return false;
}
struct ListNode* detectCycle(struct ListNode* head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast && fast->next)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            struct ListNode* meet = slow;
            while (meet != head)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return NULL;
}